/*
 * MCS.cpp
 *
 *  Created on: Sep 19, 2011
 *      Author: correa
 */

#include "StabSolvers.h"
#include <Graph.h>
#include "MCR.h"
#include <cstdlib>

int comparator1(const void* a,const void* b){
	if(a == NULL) return -1;
	if(b == NULL) return 1;
	return ((long*)a)[1] - ((long*)b)[1];
}


void MCS::pivot(int cand, int r, int* R, int * cover) {
	if(r > 3 && cand > 3){
		Graph* g = graph();
		int i,j;
		int paux, aux, paux2;
		int q = -1;
		int k2 = -1;
		int k1 = -1;
		int colors[r+1];
		int colorlist[r+1][r+1];


		memset(colors, 0, sizeof(int)*(r+1));
		for(i = 0; i < r+1; i++){
			memset(colorlist[i], 0, sizeof(int)*(r+1));
		}

		for(i = 0; i < cand; i++){
			if(g->hasEdge(R[i], R[cand])&&(cover[i] < cover[cand])){
				colorlist[cover[i]][colors[cover[i]]] = i;
				colors[cover[i]]++;
			}
		}

		for(i = cover[cand] ; i > 0; i--){
			if(colors[i] == 1){
				k1 = i;
				q = colorlist[k1][0];
			}
		}

		if((q > -1) &&(q < cand)){
			memset(colors, 0, sizeof(int)*(r+1));
			for(i = 0; i < r+1; i++){
				memset(colorlist[i], 0, sizeof(int)*(r+1));
			}
			for(i = 0; i < q; i++){
				if(g->hasEdge(R[i], R[q])&&(cover[i] < cover[cand])){
					colorlist[cover[i]][colors[cover[i]]] = i;
					colors[cover[i]]++;
				}
			}
			for(i = cover[cand] ; i > 0; i--){
				if(colors[i] == 0){
					k2 = i;
				}
			}
			//If such color exit, change colors of p and q
			if(k2 > 0){
				cover[cand] = k1;
				cover[q] = k2;
			}
		}
	}
}

void MCS::resort(subproblem* s){
	if((s!= NULL)&&(s->p > 1)){
		long order[(2*s->p)+2];
		for(int i = 0; i < s->p; i++){
			order[2*i] = s->R[i];
			order[2*i+1] = s->cover[i];
		}
		qsort(order, s->p, 2*sizeof(long),comparator1);
		for(int i = 0; i < s->p; i = i++){
			s->R[i] = order[2*i];
			s->cover[i] = order[2*i+1];
		}
	}
}

